package ACwing.P4Math.CommonDivisor;

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * @Date : 2023-03-22
 * @Description:AcWing 872. 最大公约数
 * 欧几里得算法，辗转相除法
 * d|a  d|b,则 d|ax+by， 2|6,2|4,2|4+6
 */
public class MaxCommonFactor {
    static int n;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
        n=sc.nextInt();
        while (n--!=0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            writer.println(gcd(a,b));
        }
        writer.flush();
    }
    static int gcd(int a,int b){
        return b!=0?gcd(b,a%b):a;
    }
}
